import random
from random import shuffle
class quicksortAlgorithm(object):
	"""
	"""
	def __init__(self, lista):
		super(quicksortAlgorithm, self).__init__()
		self.lista = lista



	def quicksort(self, lista, p, r):
		"""
		p - primeira posicao
		r - ultima posicao
		q - 
		"""
		if p < r:
			q = self.partition(lista, p, r)
			self.quicksort(lista, p, q-1)
			self.quicksort(lista, q+1, r)


	def partition(self, lista, p, r):
		"""
		p - primeira posicao
		r - ultima posicao
		"""
		x = lista[r]
		indice = p - 1
		for j in xrange(p, r):
			if lista[j] <= x:
				indice = indice + 1
				lista[indice], lista[j] = lista[j], lista[indice]

		lista[indice+1], lista[r] = lista[r], lista[indice+1]
		return indice+1



	def randomized_partition(self, lista, p, r):
		"""
		"""
		indice = random(p,r)
		lista[r], lista[indice] = lista[indice], lista[r]
		return self.partition(lista, p, r)

	def randomized_quicksort(self, lista, p, r):
		"""
		"""
		if p < r:
			q = self.randomized_partition(lista, p, r)
			self.randomized_quicksort(lista, p, q-1)
			self.randomized_quicksort(lista, q+1, r)

	def tail_recursive_quicksort(lista, p, r):
		"""
		"""
		while p < r:
			q = self.partition(lista, p, r)
			self.tail_recursive_quicksort(lista, p, q-1)
			p = q + 1






if __name__ == "__main__":
	lista=[]
	for i in xrange(1, 11):
		lista.append(i)
	#lista=[16,4,10,14,7,9,3,2,1,8]
	shuffle(lista)
	
	print '** Quicksort **\nLista Inicial : ', lista
	quicksortObject = quicksortAlgorithm(lista)
	quicksortObject.quicksort(lista, 0, (len(lista)-1))
	print 'Lista Ordenada: ', lista